#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, W;



vector<pair<int, int>> Products; // first表示质量, second表示价值
int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        int w, v;
        cin >> w >> v;
        Products.emplace_back(w, v);
    }
    cin >> W;

}

constexpr int MAXN = 100;
int dp[MAXN][MAXN];
// 从i开始挑选质量为j的价值最大值
int rec(int i, int j) {
    if (dp[i][j] >= 0) return dp[i][j];
    int res;
    if (i == N) return 0;
    else if (j < Products[i].first) res = rec(i + 1, j);
    else res = max(rec(i + 1, j), rec(i + 1, j - Products[i].first) + Products[i].second);
    return dp[i][j] = res;
}

// 采用动态规划的思想进行解决
void solve() {
    // dp[i][j]一种情况是物体质量大于剩余质量, 再者就是挑选价值更大的状态
    for (int i = N - 1; i >= 0; i--) {
        for (int j = 0; j <= W; j++) {
            if (Products[i].first > j) dp[i][j] = dp[i + 1][j];
            else dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - Products[i].first] + Products[i].second);
        }
    }
}

// 关键在于如何这个递推关系, 和如何解决递归时的等式关系